package 链表;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 */
public class _23_合并K个升序链表 {

    public static void main(String[] args) {

    }

    /**
     * 使用分治方法，来对lists数组进行遍历
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    /**
     * 递归遍历，找到两端中间链表，之后整合这两个链表。
     * @param lists
     * @param left
     * @param right
     * @return
     */
    public ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        if (left > right) {
            return null;
        }
        int mid = (left + right) >> 1;
        return mergeTwoList(merge(lists, left, mid), merge(lists, mid + 1, right));
    }

    /**
     * 整合两个链表
     * @param first 第一个链表
     * @param second 第二个链表
     * @return
     */
    public ListNode mergeTwoList(ListNode first, ListNode second) {
        // 如果存在一个为null 则直接返回不为null的链表
        if (first == null || second == null) {
            return first != null ? first : second;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, firstPre = first, secondPre = second;
        while (firstPre != null && secondPre != null)  {
            if (firstPre.val > secondPre.val) {
                tail.next = secondPre;
                secondPre = secondPre.next;
            }else {
                tail.next = firstPre;
                firstPre = firstPre.next;
            }
            tail = tail.next;
        }
        // 当有一个链表为null，则可以将另外的链表的值直接存入当前的链表后
        tail.next = firstPre != null ? firstPre : secondPre;
        return head.next;
    }

}
